class Solution {
 public:
  // 瞎猫碰死耗子是吧
  // 第一步不花费体力，最后一步要花费体力
  // 1. dp[i]为爬到第i梯的最小花费（后支付）
  // 2. dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
  // 3. dp[0]=0;dp[1]=0;
  // 4. i:0->n
  // 5. 检查dp数组
  /*
  int minCostClimbingStairs(vector<int>& cost) {
      int n=cost.size();
      if(n==0||n==1)
          return 0;
      vector<int>dp(n+1,0);
      int i;
      for(i=2;i<=n;i++) {
          dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
      }
      return dp[n];
  }
  */
  // 第一步花费体力，最后一步不花费体力
  // 1. dp[i]为爬到第i梯的最小花费（先支付）
  // 2. dp[i]=min(dp[i-1],dp[i-2])+cost[i];
  // 3. dp[0]=cost[0];dp[1]=cost[1];
  // 4. i:0->n
  // 5. 检查dp数组
  /*
  int minCostClimbingStairs(vector<int>& cost) {
      vector<int> dp(cost.size());
      dp[0] = cost[0];
      dp[1] = cost[1];
      for (int i = 2; i < cost.size(); i++) {
          dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
      }
      // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
      return min(dp[cost.size() - 1], dp[cost.size() - 2]);
  }
  */
  // 空间优化
  int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    int a = cost[0];
    int b = cost[1];
    int c;
    int i;
    for (i = 2; i < n; i++) {
      c = min(a, b) + cost[i];
      a = b;
      b = c;
    }
    // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
    return min(a, b);
  }
};
// 本题是L70的花费版本，题意有一点绕，采用不同的循环不变量可写出不同代码
// 同样可以进行空间优化